Γιατί η επεξεργασία ενός ταξινομημένου πίνακα γρηγορότερα από την επεξεργασία ενός μη ταξινομημένου πίνακα;

Είστε θύμα αποτυχίας πρόβλεψης κλάδου.
Τι είναι η πρόβλεψη κλάδου;
Σκεφτείτε μια διασταύρωση σιδηροδρόμου:
Εικόνα από τον Mecanismo, μέσω του Wikimedia Commons. Χρησιμοποιείται με άδεια CC-By-SA 3.0.
Τώρα για λόγους επιχειρηματολογίας, ας υποθέσουμε ότι επήλθε στη δεκαετία του 1800 - πριν από την υπεραστική ή ραδιοφωνική επικοινωνία.
Είστε ο χειριστής μιας διασταύρωσης και ακούτε ένα τρένο να έρχεται. Δεν έχετε ιδέα με ποιον τρόπο πρέπει να ακολουθήσετε. Σταματάτε το τρένο για να ρωτήσετε τον οδηγό ποια κατεύθυνση θέλει. Και μετά ρυθμίζετε κατάλληλα το διακόπτη.
Τα τρένα είναι βαριά και έχουν πολλή αδράνεια. Έτσι χρειάζονται για πάντα για να ξεκινήσουν και να επιβραδυνθούν.
Υπάρχει καλύτερος τρόπος; Υποθέτετε ποια κατεύθυνση θα ακολουθήσει το τρένο!
Αν μαντέψατε σωστά, συνεχίζεται.
Αν μαντέψατε λάθος, ο καπετάνιος θα σταματήσει, θα δημιουργήσει αντίγραφα ασφαλείας και θα σας φωνάσει για να γυρίσετε το διακόπτη. Τότε μπορεί να επανεκκινήσει την άλλη διαδρομή.
Αν μαντέψετε σωστά κάθε φορά, το τρένο δεν θα χρειαστεί ποτέ να σταματήσει. Εάν μαντέψετε πολύ συχνά, το τρένο θα αφιερώσει πολύ χρόνο σταματώντας, δημιουργώντας αντίγραφα ασφαλείας και επανεκκίνηση.
Εξετάστε μια δήλωση if: Σε επίπεδο επεξεργαστή, είναι μια εντολή κλάδου:
Είστε επεξεργαστής και βλέπετε έναν κλάδο. Δεν έχετε ιδέα με ποιον τρόπο θα πάει. Τι κάνεις? Σταματάτε την εκτέλεση και περιμένετε μέχρι να ολοκληρωθούν οι προηγούμενες οδηγίες. Στη συνέχεια, συνεχίζετε προς τη σωστή διαδρομή.
Οι σύγχρονοι επεξεργαστές είναι περίπλοκοι και έχουν μεγάλους αγωγούς. Έτσι παίρνουν για πάντα να «ζεσταθούν» και «να επιβραδυνθούν».
Υπάρχει καλύτερος τρόπος; Υποθέτετε ποια κατεύθυνση θα πάει το υποκατάστημα!
Εάν μαντέψατε σωστά, συνεχίζετε να εκτελείτε.
Εάν μαντέψατε λάθος, πρέπει να ξεπλύνετε τον αγωγό και να γυρίσετε πίσω στον κλάδο. Στη συνέχεια, μπορείτε να κάνετε επανεκκίνηση στην άλλη διαδρομή.
Εάν μαντέψετε σωστά κάθε φορά, η εκτέλεση δεν θα χρειαστεί ποτέ να σταματήσει. Εάν μαντέψετε πολύ συχνά λάθος, ξοδεύετε πολύ χρόνο καθυστέρηση, επαναφορά και επανεκκίνηση.
Αυτή είναι πρόβλεψη κλάδου. Παραδέχομαι ότι δεν είναι η καλύτερη αναλογία, καθώς το τρένο θα μπορούσε απλώς να σηματοδοτήσει την κατεύθυνση με μια σημαία. Όμως, στους υπολογιστές, ο επεξεργαστής δεν γνωρίζει ποια κατεύθυνση θα διανύσει ένας κλάδος μέχρι την τελευταία στιγμή.
Λοιπόν, πώς θα μαντέψατε στρατηγικά για να ελαχιστοποιήσετε τον αριθμό των φορών που το τρένο πρέπει να δημιουργήσει αντίγραφα ασφαλείας και να ακολουθήσει το άλλο μονοπάτι; Κοιτάς την ιστορία του παρελθόντος! Εάν η αμαξοστοιχία πάει αριστερά το 99% του χρόνου, τότε μαντέψετε αριστερά. Εάν εναλλάσσεται, τότε εναλλάσσετε τις εικασίες σας. Εάν πηγαίνει μονόδρομος κάθε τρεις φορές, υποθέτετε το ίδιο ...
Με άλλα λόγια, προσπαθείτε να προσδιορίσετε ένα μοτίβο και να το ακολουθήσετε. Αυτό είναι λίγο πολύ πώς λειτουργούν οι προβλέψεις κλάδων.
Οι περισσότερες εφαρμογές έχουν κλάδους καλής συμπεριφοράς. Έτσι, οι σύγχρονοι προγνωστικοί κλάδοι θα επιτύχουν συνήθως> 90% ποσοστά επιτυχίας. Αλλά όταν αντιμετωπίζουν απρόβλεπτα κλαδιά χωρίς αναγνωρίσιμα μοτίβα, οι προβλέψεις κλάδων είναι σχεδόν άχρηστοι.
Περαιτέρω ανάγνωση: άρθρο "Πρόβλεψη κλάδου" στη Wikipedia.
Όπως υπαινίχθηκε από ψηλά, ο ένοχος είναι αυτή η δήλωση if:
εάν (δεδομένα [c]> = 128)
άθροισμα + = δεδομένα [c];
Παρατηρήστε ότι τα δεδομένα κατανέμονται ομοιόμορφα μεταξύ 0 και 255. Όταν τα δεδομένα ταξινομηθούν, περίπου το πρώτο μισό των επαναλήψεων δεν θα εισέλθει στο if-statement. Μετά από αυτό, θα εισαγάγουν όλοι το if-statement.
Αυτό είναι πολύ φιλικό προς τον προγνωστικό κλάδο καθώς το υποκατάστημα ακολουθεί διαδοχικά την ίδια κατεύθυνση πολλές φορές. Ακόμη και ένας απλός μετρητής κορεσμού θα προβλέψει σωστά τον κλάδο εκτός από τις λίγες επαναλήψεις μετά την αλλαγή κατεύθυνσης.
Γρήγορη οπτικοποίηση:
T = το υποκατάστημα έχει ληφθεί
N = το υποκατάστημα δεν έχει ληφθεί
δεδομένα [] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
υποκατάστημα = N N N N N ... N N T T T ... T T T ...
= NNNNNNNNNNNN ... NNNNNNNTTTTTTTT ... TTTTTTTTTT (εύκολο να προβλεφθεί)
Ωστόσο, όταν τα δεδομένα είναι εντελώς τυχαία, η πρόβλεψη κλάδου καθίσταται άχρηστη, επειδή δεν μπορεί να προβλέψει τυχαία δεδομένα. Κατά συνέπεια, πιθανότατα θα υπάρχει περίπου 50% λανθασμένη πρόβλεψη (όχι καλύτερη από τυχαία εικασία).
δεδομένα [] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118, 14, 150, 177, 182, 133, ...
υποκατάστημα = T, T, N, T, T, T, T, N, T, N, N, T, T, T, N ...
= TTNTTTTNTNNTTTN ... (εντελώς τυχαίο - δύσκολο να προβλεφθεί)
Τι μπορεί να γίνει λοιπόν;
Εάν ο μεταγλωττιστής δεν είναι σε θέση να βελτιστοποιήσει τον κλάδο σε κίνηση υπό όρους, μπορείτε να δοκιμάσετε κάποιες παραβιάσεις αν θέλετε να θυσιάσετε την αναγνωσιμότητα για απόδοση.
Αντικαθιστώ:
εάν (δεδομένα [c]> = 128)
άθροισμα + = δεδομένα [c];
με:
int t = (δεδομένα [c] - 128) >> 31;
άθροισμα + = ~ t & δεδομένα [c];
Αυτό εξαλείφει τον κλάδο και το αντικαθιστά με κάποιες λειτουργίες bitwise.
(Λάβετε υπόψη ότι αυτή η παραβίαση δεν είναι αυστηρά ισοδύναμη με την αρχική δήλωση if. Αλλά σε αυτήν την περίπτωση, ισχύει για όλες τις τιμές εισαγωγής δεδομένων [].)
Σημεία αναφοράς: Core i7 920 @ 3,5 GHz
C ++ - Visual Studio 2010 - Έκδοση x64
// Υποκατάστημα - Τυχαία
δευτερόλεπτα = 11.777
// Υποκατάστημα - Ταξινόμηση
δευτερόλεπτα = 2.352
// Χωρίς κλάδο - Τυχαίο
δευτερόλεπτα = 2.564
// Χωρίς κλάδο - Ταξινόμηση
δευτερόλεπτα = 2.587
Java - NetBeans 7.1.1 JDK 7 - x64
// Υποκατάστημα - Τυχαία
δευτερόλεπτα = 10.93293813
// Υποκατάστημα - Ταξινόμηση
δευτερόλεπτα = 5.643797077
// Χωρίς κλάδο -Τυχαίος
δευτερόλεπτα = 3.113581453
// Χωρίς κλάδο - Ταξινόμηση
δευτερόλεπτα = 3.186068823
Παρατηρήσεις:
Με το Branch: Υπάρχει μια τεράστια διαφορά μεταξύ των ταξινομημένων και των μη ταξινομημένων δεδομένων.
Με το Hack: Δεν υπάρχει διαφορά μεταξύ ταξινομημένων και μη ταξινομημένων δεδομένων.
Στην περίπτωση C ++, το hack είναι στην πραγματικότητα λίγο πιο αργό από ό, τι με τον κλάδο κατά την ταξινόμηση των δεδομένων.
Ένας γενικός κανόνας είναι η αποφυγή διακλάδωσης που εξαρτάται από δεδομένα σε κρίσιμους βρόχους (όπως σε αυτό το παράδειγμα).
Εκσυγχρονίζω:
Το GCC 4.6.1 με -O3 ή -free-vectorize στο x64 είναι σε θέση να δημιουργήσει μια κίνηση υπό όρους. Επομένως, δεν υπάρχει διαφορά μεταξύ των ταξινομημένων και μη ταξινομημένων δεδομένων - και τα δύο είναι γρήγορα.
(Ή κάπως γρήγορα: για την ήδη ταξινομημένη περίπτωση, το cmov μπορεί να είναι πιο αργό ειδικά αν το GCC το βάζει στην κρίσιμη διαδρομή αντί να προσθέσει, ειδικά στην Intel πριν από το Broadwell όπου το cmov έχει καθυστέρηση 2 κύκλων: η σημαία βελτιστοποίησης gcc -O3 καθιστά τον κώδικα πιο αργό από -O2)
Το VC ++ 2010 δεν μπορεί να δημιουργήσει κινήσεις υπό όρους για αυτόν τον κλάδο ακόμη και κάτω από το / Ox.
Το Intel C ++ Compiler (ICC) 11 κάνει κάτι θαυμαστό. Ανταλλάσσει τους δύο βρόχους, ανυψώνοντας έτσι τον απρόβλεπτο κλάδο στον εξωτερικό βρόχο. Επομένως, όχι μόνο είναι άνοσο στις εσφαλμένες προβλέψεις, αλλά είναι επίσης διπλάσιο από ό, τι μπορεί να δημιουργήσει το VC ++ και το GCC! Με άλλα λόγια, το ICC εκμεταλλεύτηκε τον δοκιμαστικό βρόχο για να νικήσει το σημείο αναφοράς ...
Εάν δώσετε στον μεταγλωττιστή Intel τον κωδικό χωρίς διακλαδώσεις, τον εξατομικεύει ακριβώς έξω ... και είναι εξίσου γρήγορος με τον κλάδο (με την εναλλαγή βρόχου).
Αυτό δείχνει ότι ακόμη και οι ώριμοι σύγχρονοι μεταγλωττιστές μπορούν να διαφέρουν έντονα στην ικανότητά τους να βελτιστοποιούν τον κώδικα ...
|
Πρόβλεψη κλάδου.
Με έναν ταξινομημένο πίνακα, τα δεδομένα συνθήκης [c]> = 128 είναι πρώτα ψευδώς για μια σειρά τιμών και μετά γίνονται αληθή για όλες τις μεταγενέστερες τιμές. Αυτό είναι εύκολο να προβλεφθεί. Με έναν μη ταξινομημένο πίνακα, πληρώνετε για το κόστος διακλάδωσης.
|
Ο λόγος για τον οποίο η απόδοση βελτιώνεται δραστικά όταν ταξινομηθούν τα δεδομένα είναι ότι αφαιρείται η ποινή πρόβλεψης κλάδου, όπως εξηγείται όμορφα στην απάντηση του Mysticial.
Τώρα, αν κοιτάξουμε τον κώδικα
εάν (δεδομένα [c]> = 128)
άθροισμα + = δεδομένα [c];
μπορούμε να βρούμε ότι η έννοια αυτού του συγκεκριμένου αν ... αλλιώς ... υποκατάστημα είναι να προσθέσουμε κάτι όταν ικανοποιείται μια συνθήκη. Αυτός ο τύπος κλάδου μπορεί εύκολα να μετατραπεί σε μια δήλωση κίνησης υπό όρους, η οποία θα μεταγλωττίστηκε σε μια εντολή κίνησης υπό όρους: cmovl, σε ένα σύστημα x86. Το υποκατάστημα και έτσι η πιθανή ποινή πρόβλεψης κλάδου αφαιρείται.
Στο C, έτσι C ++, η δήλωση, η οποία θα μεταγλώττιζε απευθείας (χωρίς καμία βελτιστοποίηση) στην υπό όρους εντολή κίνησης στο x86, είναι ο τριμελής τελεστής ...; ...: .... Γι 'αυτό ξαναγράφουμε την παραπάνω δήλωση σε ισοδύναμη:
άθροισμα + = δεδομένα [c]> = 128; δεδομένα [c]: 0;
Ενώ διατηρούμε την αναγνωσιμότητα, μπορούμε να ελέγξουμε τον συντελεστή επιτάχυνσης.
Σε λειτουργία απελευθέρωσης Intel Core i7-2600K @ 3,4 GHz και Visual Studio 2010, το σημείο αναφοράς είναι (η μορφή αντιγράφηκε από το Mysticial):
x86
// Υποκατάστημα - Τυχαία
δευτερόλεπτα = 8.885
// Υποκατάστημα - Ταξινόμηση
δευτερόλεπτα = 1,528
// Χωρίς κλάδο - Τυχαίο
δευτερόλεπτα = 3.716
// Χωρίς κλάδο - Ταξινόμηση
δευτερόλεπτα = 3,71
x64
// Υποκατάστημα - Τυχαία
δευτερόλεπτα = 11.302
// Υποκατάστημα - Ταξινόμηση
δευτερόλεπτα = 1.830
// Χωρίς κλάδο - Τυχαίο
δευτερόλεπτα = 2.736
// Χωρίς κλάδο - Ταξινόμηση
δευτερόλεπτα = 2.737
Το αποτέλεσμα είναι ισχυρό σε πολλές δοκιμές. Παίρνουμε μεγάλη ταχύτητα όταν το αποτέλεσμα του κλάδου είναι απρόβλεπτο, αλλά υποφέρουμε λίγο όταν είναι προβλέψιμο. Στην πραγματικότητα, όταν χρησιμοποιείτε μια κίνηση υπό όρους, η απόδοση είναι η ίδια ανεξάρτητα από το μοτίβο δεδομένων.
Τώρα ας δούμε πιο προσεκτικά διερευνώντας τη συναρμολόγηση x86 που δημιουργούν. Για απλότητα, χρησιμοποιούμε δύο συναρτήσεις max1 και max2.
Το max1 χρησιμοποιεί τον υποκατάστημα υπό όρους εάν ... αλλιώς ...:
int max1 (int a, int b) {
αν (α> β)
επιστροφή α?
αλλού
επιστροφή β;
}
Το max2 χρησιμοποιεί τον τριμερή τελεστή ...; ...: ...:
int max2 (int a, int b) {
επιστροφή a> b; α: β;
}
Σε μηχανή x86-64, το GCC -S δημιουργεί τη συναρμολόγηση παρακάτω.
: max1
movl% edi, -4 (% rbp)
movl% esi, -8 (% rbp)
movl -4 (% rbp),% eax
cmpl -8 (% rbp),% eax
jle .L2
movl -4 (% rbp),% eax
movl% eax, -12 (% rbp)
jmp. L4
.L2:
movl -8 (% rbp),% eax
movl% eax, -12 (% rbp)
.L4:
movl -12 (% rbp),% eax
άδεια
μουσκεύω
: max2
movl% edi, -4 (% rbp)
movl% esi, -8 (% rbp)
movl -4 (% rbp),% eax
cmpl% eax, -8 (% rbp)
cmovge -8 (% rbp),% eax
άδεια
μουσκεύω
Το max2 χρησιμοποιεί πολύ λιγότερο κώδικα λόγω της χρήσης της εντολής cmovge. Αλλά το πραγματικό κέρδος είναι ότι το max2 δεν περιλαμβάνει άλματα κλάδου, jmp, το οποίο θα είχε σημαντική ποινή απόδοσης εάν το προβλεπόμενο αποτέλεσμα δεν είναι σωστό.
Γιατί λοιπόν η απόδοση υπό όρους λειτουργεί καλύτερα;
Σε έναν τυπικό επεξεργαστή x86, η εκτέλεση μιας εντολής χωρίζεται σε διάφορα στάδια. Κατά προσέγγιση, έχουμε διαφορετικό υλικό για να αντιμετωπίσουμε διαφορετικά στάδια. Επομένως, δεν χρειάζεται να περιμένουμε να ολοκληρωθεί μία οδηγία για να ξεκινήσει μια νέα. Αυτό ονομάζεται σωληνώσεις.
Σε μια περίπτωση κλάδου, η ακόλουθη οδηγία καθορίζεται από την προηγούμενη, οπότε δεν μπορούμε να κάνουμε σωληνώσεις. Πρέπει είτε να περιμένουμε είτε να προβλέψουμε.
Σε υπόθεση κίνησης υπό όρους,Η εντολή μετακίνησης υπό όρους εκτέλεσης χωρίζεται σε διάφορα στάδια, αλλά τα προηγούμενα στάδια όπως το Fetch και το Decode δεν εξαρτώνται από το αποτέλεσμα της προηγούμενης εντολής μόνο τα τελευταία στάδια χρειάζονται το αποτέλεσμα. Έτσι, περιμένουμε ένα κλάσμα του χρόνου εκτέλεσης μιας εντολής. Αυτός είναι ο λόγος για τον οποίο η έκδοση υπό όρους κίνησης είναι πιο αργή από τον κλάδο όταν η πρόβλεψη είναι εύκολη.
Το βιβλίο Computer Systems: A Programmer's Perspective, δεύτερη έκδοση το εξηγεί λεπτομερώς. Μπορείτε να ελέγξετε την Ενότητα 3.6.6 για Οδηγίες Μετακίνησης υπό όρους, ολόκληρο το Κεφάλαιο 4 για την Αρχιτεκτονική του Επεξεργαστή και την Ενότητα 5.11.2 για ειδική μεταχείριση για τις Κυρώσεις Πρόβλεψης και Εσφαλμένης Πρόβλεψης.
Μερικές φορές, ορισμένοι σύγχρονοι μεταγλωττιστές μπορούν να βελτιστοποιήσουν τον κώδικα μας για συναρμολόγηση με καλύτερη απόδοση, μερικές φορές ορισμένοι μεταγλωττιστές δεν μπορούν (ο εν λόγω κωδικός χρησιμοποιεί τον εγγενή μεταγλωττιστή του Visual Studio). Γνωρίζοντας τη διαφορά απόδοσης μεταξύ ενός κλάδου και μιας υπό όρους κίνησης όταν είναι απρόβλεπτο μπορεί να μας βοηθήσει να γράψουμε κώδικα με καλύτερη απόδοση όταν το σενάριο γίνεται τόσο περίπλοκο που ο μεταγλωττιστής δεν μπορεί να τους βελτιστοποιήσει αυτόματα.
|
Εάν είστε περίεργοι για ακόμη περισσότερες βελτιστοποιήσεις που μπορούν να γίνουν σε αυτόν τον κώδικα, σκεφτείτε το εξής:
Ξεκινώντας με τον αρχικό βρόχο:
για (χωρίς υπογραφή i = 0; i <100000; ++ i)
{
για (χωρίς υπογραφή j = 0; j  = 128)
άθροισμα + = δεδομένα [j];
}
}
Με την εναλλαγή βρόχου, μπορούμε να αλλάξουμε με ασφάλεια αυτόν τον βρόχο σε:
για (χωρίς υπογραφή j = 0; j  = 128)
άθροισμα + = δεδομένα [j];
}
}
Στη συνέχεια, μπορείτε να δείτε ότι το if υπό όρους είναι σταθερό καθ 'όλη την εκτέλεση του i loop, οπότε μπορείτε να ανυψώσετε το if out:
για (χωρίς υπογραφή j = 0; j  = 128)
{
για (χωρίς υπογραφή i = 0; i <100000; ++ i)
{
άθροισμα + = δεδομένα [j];
}
}
}
Στη συνέχεια, βλέπετε ότι ο εσωτερικός βρόχος μπορεί να καταρρεύσει σε μία μεμονωμένη έκφραση, υποθέτοντας ότι το μοντέλο κινούμενου σημείου το επιτρέπει (/ fp: γρήγορη ρίψη, για παράδειγμα)
για (χωρίς υπογραφή j = 0; j  = 128)
{
άθροισμα + = δεδομένα [j] * 100000;
}
}
Αυτό είναι 100.000 φορές γρηγορότερο από πριν.
|
Χωρίς αμφιβολία, ορισμένοι από εμάς θα ενδιαφερόμαστε για τρόπους αναγνώρισης κώδικα που είναι προβληματικός για την πρόβλεψη κλάδου της CPU. Το εργαλείο Valgrind cachegrind διαθέτει προσομοιωτή πρόβλεψης κλάδου, ενεργοποιημένο χρησιμοποιώντας τη σημαία --branch-sim = yes. Τρέχοντας τα παραδείγματα σε αυτήν την ερώτηση, με τον αριθμό των εξωτερικών βρόχων να μειωθεί σε 10000 και να μεταγλωττιστεί με g ++, δίνει αυτά τα αποτελέσματα:
Ταξινομημένο:
== 32551 == Υποκαταστήματα: 656.645.130 (656.609.208 cond + 35.922 ind)
== 32551 == Παρεμβάσεις: 169.556 (169.095 cond + 461 ind)
== 32551 == Ποσοστό εσφαλμένου ποσοστού: 0,0% (0,0% + 1,2%)
Χωρίς ταξινόμηση:
== 32555 == Υποκαταστήματα: 655,996,082 (655,960,160 cond + 35,922 ind)
== 32555 == Ανεπιθύμητες προβλέψεις: 164.073.152 (164.072.692 cond + 460 ind)
== 32555 == Ποσοστό εσφαλμένου ποσοστού: 25,0% (25,0% + 1,2%)
Αναλύοντας την έξοδο γραμμής προς γραμμή που παράγεται από το cg_annotate βλέπουμε για τον εν λόγω βρόχο:
Ταξινομημένο:
Bc Bcm Bi Bim
10,001 4 0 0 για (χωρίς υπογραφή i = 0; i <10000; ++ i)
. . . . {
. . . . // πρωτεύον βρόχο
327.690.000 10.016 0 0 για (χωρίς υπογραφή c = 0; c  = 128)
0 0 0 0 άθροισμα + = δεδομένα [c];
. . . . }
. . . . }
Χωρίς ταξινόμηση:
Bc Bcm Bi Bim
10,001 4 0 0 για (χωρίς υπογραφή i = 0; i <10000; ++ i)
. . . . {
. . . . // πρωτεύον βρόχο
327.690.000 10.038 0 0 για (χωρίς υπογραφή c = 0; c  = 128)
0 0 0 0 άθροισμα + = δεδομένα [c];
. . . . }
. . . . }
Αυτό σας επιτρέπει να αναγνωρίσετε εύκολα την προβληματική γραμμή - στην μη ταξινομημένη έκδοση η γραμμή if (data [c]> = 128) προκαλεί 164.050.007 εσφαλμένους προβλεπόμενους κλάδους (Bcm) κάτω από το μοντέλο πρόβλεψης κλάδου cachegrind, ενώ προκαλεί μόνο 10.006 στην ταξινομημένη έκδοση .
Εναλλακτικά, στο Linux μπορείτε να χρησιμοποιήσετε το υποσύστημα μετρητών επιδόσεων για να ολοκληρώσετε την ίδια εργασία, αλλά με εγγενή απόδοση χρησιμοποιώντας μετρητές CPU.
perf stat ./sumtest_s ταξινομημένο
Ταξινομημένο:
Στατιστικά μετρητών επιδόσεων για "./sumtest_sorted":
11808.095776 task-clock # 0.998 CPU που χρησιμοποιήθηκαν
1.062 διακόπτες περιβάλλοντος # 0,090 K / sec
14 CPU-μετεγκαταστάσεις # 0,001 K / sec
337 σελίδα-σφάλματα # 0,029 K / sec
26.487.882.764 κύκλοι # 2.243 GHz
41.025.654.322 οδηγίες # 1,55 insns ανά κύκλο
6.558.871.379 κλάδοι # 555.455 Μ / δευτ
567.204 υποκατάστημα-χάνει # 0,01% όλων των κλάδων
Πέρασε ο χρόνος 11.827228330 δευτερολέπτων
Χωρίς ταξινόμηση:
Εκτέλεσημετρητές στατιστικών για './sumtest_unsorted':
28877.954344 ρολόι εργασιών # 0,998 Χρησιμοποιήθηκαν CPU
2.584 διακόπτες περιβάλλοντος # 0,089 K / sec
18 CPU-μετεγκαταστάσεις # 0,001 K / sec
335 σελίδα-σφάλματα # 0,012 K / sec
65.076.127.595 κύκλοι # 2.253 GHz
41.032.528.741 οδηγίες # 0.63 insns ανά κύκλο
6.560.579.013 κλάδοι # 227.183 M / sec
1.646.394.749 υποκατάστημα-απώλειες # 25,10% όλων των κλάδων
Πέρασε ο χρόνος 28.935500947 δευτερολέπτων
Μπορεί επίσης να κάνει σχολιασμό πηγαίου κώδικα με αποσυναρμολόγηση.
perf record -e branch-misses ./sumtest_unsorted
perf annotate -d sumtest_unsorted
Ποσοστό | Πηγαίος κώδικας και αποσυναρμολόγηση του sumtest_unsorted
------------------------------------------------
...
: άθροισμα + = δεδομένα [c];
0,00: 400a1a: mov -0x14 (% rbp),% eax
39.97: 400a1d: mov% eax,% eax
5.31: 400a1f: mov -0x20040 (% rbp,% rax, 4),% eax
4.60: 400a26: cltq
0,00: 400a28: προσθήκη% rax, -0x30 (% rbp)
...
Δείτε το φροντιστήριο απόδοσης για περισσότερες λεπτομέρειες.
|
Μόλις διάβασα αυτήν την ερώτηση και τις απαντήσεις της και αισθάνομαι ότι λείπει μια απάντηση.
Ένας κοινός τρόπος για την εξάλειψη της πρόβλεψης κλάδου που έχω διαπιστώσει ότι λειτουργεί ιδιαίτερα καλά σε διαχειριζόμενες γλώσσες είναι η αναζήτηση πίνακα αντί της χρήσης κλάδου (αν και δεν το έχω δοκιμάσει σε αυτήν την περίπτωση).
Αυτή η προσέγγιση λειτουργεί γενικά εάν:
είναι ένας μικρός πίνακας και είναι πιθανό να αποθηκευτεί στην κρυφή μνήμη στον επεξεργαστή και
εκτελείτε πράγματα σε έναν πολύ στενό βρόχο και / ή ο επεξεργαστής μπορεί να προφορτώσει τα δεδομένα.
Ιστορικό και γιατί
Από τη σκοπιά του επεξεργαστή, η μνήμη σας είναι αργή. Για να αντισταθμιστεί η διαφορά στην ταχύτητα, μερικά cache ενσωματώνονται στον επεξεργαστή σας (L1 / L2 cache). Φανταστείτε λοιπόν ότι κάνετε τους ωραίους υπολογισμούς σας και καταλάβετε ότι χρειάζεστε μια μνήμη. Ο επεξεργαστής θα πάρει τη λειτουργία «φόρτωσης» και φορτώνει το κομμάτι της μνήμης στην προσωρινή μνήμη - και στη συνέχεια χρησιμοποιεί την προσωρινή μνήμη για να κάνει τους υπόλοιπους υπολογισμούς. Επειδή η μνήμη είναι σχετικά αργή, αυτή η «φόρτωση» θα επιβραδύνει το πρόγραμμά σας.
Όπως και η πρόβλεψη κλάδου, αυτό βελτιστοποιήθηκε στους επεξεργαστές Pentium: ο επεξεργαστής προβλέπει ότι πρέπει να φορτώσει ένα κομμάτι δεδομένων και προσπαθεί να το φορτώσει στην προσωρινή μνήμη προτού η λειτουργία φτάσει πραγματικά στην προσωρινή μνήμη. Όπως έχουμε ήδη δει, η πρόβλεψη κλάδου μερικές φορές πάει πολύ άσχημα - στη χειρότερη περίπτωση πρέπει να επιστρέψετε και να περιμένετε πραγματικά για ένα φορτίο μνήμης, το οποίο θα διαρκέσει για πάντα (με άλλα λόγια: η αποτυχία πρόβλεψης κλάδου είναι κακή, μια μνήμη φόρτωση μετά την αποτυχία πρόβλεψης κλάδου είναι απλώς φρικτό!).
Ευτυχώς για εμάς, εάν το μοτίβο πρόσβασης στη μνήμη είναι προβλέψιμο, ο επεξεργαστής θα το φορτώσει στη γρήγορη προσωρινή μνήμη και όλα είναι καλά.
Το πρώτο πράγμα που πρέπει να γνωρίζουμε είναι τι είναι μικρό; Ενώ το μικρότερο είναι γενικά καλύτερο, ένας κανόνας είναι να κολλήσετε σε πίνακες αναζήτησης που έχουν μέγεθος <= 4096 byte. Ως ανώτερο όριο: εάν ο πίνακας αναζήτησης είναι μεγαλύτερος από 64K, πιθανώς αξίζει να το επανεξετάσετε.
Κατασκευή τραπεζιού
Έτσι, καταλάβαμε ότι μπορούμε να δημιουργήσουμε ένα μικρό τραπέζι. Το επόμενο πράγμα που πρέπει να κάνετε είναι να δημιουργήσετε μια λειτουργία αναζήτησης. Οι συναρτήσεις αναζήτησης είναι συνήθως μικρές λειτουργίες που χρησιμοποιούν μερικές βασικές ακέραιες λειτουργίες (και, ή, xor, shift, add, remove και ίσως πολλαπλασιάζονται). Θέλετε να μεταφράσετε τη συμβολή σας από τη λειτουργία αναζήτησης σε κάποιο είδος «μοναδικού κλειδιού» στον πίνακα σας, το οποίο στη συνέχεια απλώς σας δίνει την απάντηση όλης της εργασίας που θέλετε να κάνει.
Σε αυτήν την περίπτωση:> = 128 σημαίνει ότι μπορούμε να διατηρήσουμε την τιμή, <128 σημαίνει να την ξεφορτωθούμε. Ο ευκολότερος τρόπος για να γίνει αυτό είναι με τη χρήση ενός «ΚΑΙ»: αν το διατηρήσουμε, εμείς ΚΑΙ το με 7FFFFFFF. αν θέλουμε να το ξεφορτωθούμε, εμείς ΚΑΙ με 0. Σημειώστε επίσης ότι το 128 είναι δύναμη 2 - έτσι μπορούμε να προχωρήσουμε και να φτιάξουμε έναν πίνακα 32768/128 ακέραιων αριθμών και να το γεμίσουμε με ένα μηδέν και πολλά 7FFFFFFFF's.
Διαχειριζόμενες γλώσσες
Ίσως αναρωτιέστε γιατί αυτό λειτουργεί καλά σε διαχειριζόμενες γλώσσες. Σε τελική ανάλυση, οι διαχειριζόμενες γλώσσες ελέγχουν τα όρια των συστοιχιών με ένα κλαδί για να διασφαλίσουν ότι δεν θα χάσετε ...
Λοιπόν, όχι ακριβώς ... :-)
Υπήρξε αρκετή δουλειά για την εξάλειψη αυτού του κλάδου για διαχειριζόμενες γλώσσες. Για παράδειγμα:
για (int i = 0; i  = 128); γ: 0;
}
// Δοκιμή
DateTime startTime = System.DateTime.Now;
μεγάλο ποσό = 0;
για (int i = 0; i <100000; ++ i)
{
// Κύριος βρόχος
για (int j = 0; j  = 128. Αυτό σημαίνει ότι μπορούμε εύκολα να εξαγάγουμε ένα μόνο κομμάτι που θα μας πει αν θέλουμε μια τιμή ή όχι: μετατοπίζοντας τα δεδομένα στα δεξιά 7 bits, μένουν με 0 bit ή 1 bit και θέλουμε να προσθέσουμε την τιμή μόνο όταν έχουμε 1 bit. Ας το ονομάσουμε αυτό το κομμάτι "bit απόφασης".
Χρησιμοποιώντας την τιμή 0/1 του bit απόφασης ως ευρετήριο σε έναν πίνακα, μπορούμε να φτιάξουμε κώδικα που θα είναι εξίσου γρήγορος είτε τα δεδομένα ταξινομούνται είτε όχι. Ο κώδικάς μας θα προσθέτει πάντα μια τιμή, αλλά όταν το bit απόφασης είναι 0, θα προσθέσουμε την τιμή κάπου που δεν μας ενδιαφέρει. Εδώ είναι ο κωδικός:
// Δοκιμή
clock_t start = ρολόι ();
πολύ καιρό a [] = {0, 0};
πολύ μεγάλο ποσό
για (χωρίς υπογραφή i = 0; i <100000; ++ i)
{
// Κύριος βρόχος
για (χωρίς υπογραφή c = 0; c > 7);
a [j] + = δεδομένα [c];
}
}
double elapsedTime = static_cast  (ρολόι () - έναρξη) / CLOCKS_PER_SEC;
άθροισμα = α [1];
Αυτός ο κώδικας σπαταλά τα μισά από τα πρόσθετα αλλά δεν έχει ποτέ αποτυχία πρόβλεψης κλάδου. Είναι πολύ πιο γρήγορα σε τυχαία δεδομένα από την έκδοση με μια πραγματική δήλωση if.
Αλλά στις δοκιμές μου, ένας σαφής πίνακας αναζήτησης ήταν ελαφρώς πιο γρήγορος από αυτό, πιθανώς επειδή η ευρετηρίαση σε έναν πίνακα αναζήτησης ήταν ελαφρώς πιο γρήγορη από την αλλαγή bit. Αυτό δείχνει τον τρόπο με τον οποίο ο κώδικάς μου δημιουργεί και χρησιμοποιεί τον πίνακα αναζήτησης (χωρίς φαντασία ονομάζεται lut για το "LookUp Table" στον κώδικα). Εδώ είναι ο κωδικός C ++:
// Δηλώστε και, στη συνέχεια, συμπληρώστε τον πίνακα αναζήτησης
int lut [256];
για (χωρίς υπογραφή c = 0; c <256; ++ c)
lut [c] = (c> = 128); γ: 0;
// Χρησιμοποιήστε τον πίνακα αναζήτησης μετά τη δημιουργία του
για (χωρίς υπογραφή i = 0; i <100000; ++ i)
{
// Κύριος βρόχος
για (χωρίς υπογραφή c = 0; c )
κόμβος = κόμβος-> pLeft;
αλλού
node = node-> pRight;
αυτή η βιβλιοθήκη θα έκανε κάτι σαν:
i = (x  τιμή);
node = node-> σύνδεσμος [i];
Ακολουθεί ένας σύνδεσμος για αυτόν τον κωδικό: Κόκκινα Μαύρα Δέντρα, Eternally Confuzzled
|
Στην ταξινομημένη περίπτωση, μπορείτε να κάνετε καλύτερα από το να βασιστείτε σε επιτυχημένη πρόβλεψη κλάδου ή σε οποιοδήποτε κόλπο σύγκρισης χωρίς κλάδο: αφαιρέστε εντελώς τον κλάδο.
Πράγματι, ο πίνακας χωρίζεται σε γειτονική ζώνη με δεδομένα <128 και άλλο με δεδομένα> = 128. Επομένως, θα πρέπει να βρείτε το σημείο διαμέρισης με διχοτομική αναζήτηση (χρησιμοποιώντας Lg (arraySize) = 15 συγκρίσεις) και, στη συνέχεια, κάντε μια ευθεία συσσώρευση από αυτό το σημείο.
Κάτι σαν (μη επιλεγμένο)
int i = 0, j, k = arraySize;
ενώ (i > 1;
εάν (δεδομένα [j]> = 128)
k = j;
αλλού
i = j;
}
άθροισμα = 0;
για (; i > 1;
για (i = 0, k = arraySize; i  = 128? k: i) = j)
j = (i + k) >> 1;
για (άθροισμα = 0; i  = 128)
/ \
/ \
/ \
Σωστό Λάθος
/ \
/ \
/ \
/ \
B) άθροισμα + = δεδομένα [c]; Γ) για βρόχο ή εκτύπωση ().
Χωρίς πρόβλεψη κλάδου, θα συμβούν τα εξής:
Για την εκτέλεση της εντολής B ή της εντολής C, ο επεξεργαστής θα πρέπει να περιμένει έως ότου η εντολή A δεν φτάσει μέχρι το στάδιο EX στον αγωγό, καθώς η απόφαση για μετάβαση στην οδηγία B ή στην οδηγία C εξαρτάται από το αποτέλεσμα της εντολής A. Έτσι, ο αγωγός θα μοιάζει με αυτό.
όταν εάν η συνθήκη επιστρέφει αληθής:
Όταν εάν η συνθήκη επιστρέφει ψευδής:
Ως αποτέλεσμα της αναμονής για το αποτέλεσμα της εντολής Α, οι συνολικοί κύκλοι CPU που δαπανήθηκαν στην παραπάνω περίπτωση (χωρίς πρόβλεψη κλάδου · για αληθές και ψευδές) είναι 7.
Τι είναι λοιπόν η πρόβλεψη κλάδου;
Η πρόβλεψη διακλάδωσης θα προσπαθήσει να μαντέψει με ποιον τρόπο θα προχωρήσει ένας κλάδος (μια δομή αν-τότε-αλλιώς) προτού αυτό είναι γνωστό. Δεν θα περιμένει την εντολή Α να φτάσει στο στάδιο EX του αγωγού, αλλά θα μαντέψει την απόφαση και θα πάει σε αυτήν την οδηγία (B ή C στην περίπτωση του παραδείγματος μας).
Σε περίπτωση σωστής εικασίας, ο αγωγός μοιάζει με αυτό:
Εάν αργότερα εντοπιστεί ότι η εικασία ήταν λανθασμένη, οι οδηγίες που εκτελέστηκαν μερικώς απορρίπτονται και ο αγωγός ξεκινά με τον σωστό κλάδο, με αποτέλεσμα να καθυστερήσει.
Ο χρόνος που χάνεται σε περίπτωση εσφαλμένης πρόβλεψης διακλάδωσης ισούται με τον αριθμό των σταδίων του αγωγού από το στάδιο λήψης έως το στάδιο εκτέλεσης. Οι σύγχρονοι μικροεπεξεργαστές τείνουν να έχουν αρκετά μεγάλους αγωγούς, έτσι ώστε η καθυστέρηση λανθασμένης πρόβλεψης να κυμαίνεται μεταξύ 10 και 20 κύκλων ρολογιού. Όσο μεγαλύτερος είναι ο αγωγός τόσο μεγαλύτερη είναι η ανάγκη για έναν καλό προγνωστικό κλάδο.
Στον κώδικα του OP, την πρώτη φορά που ο υπό όρους, ο προγνωστής κλάδου δεν έχει καμία πληροφορία για να βασίσει την πρόβλεψη, οπότε την πρώτη φορά θα επιλέξει τυχαία την επόμενη οδηγία. Αργότερα στο loop for, μπορεί να βασίσει την πρόβλεψη στο ιστορικό.
Για έναν πίνακα ταξινομημένο σε αύξουσα σειρά, υπάρχουν τρεις δυνατότητες:
Όλα τα στοιχεία είναι μικρότερα από 128
Όλα τα στοιχεία είναι μεγαλύτερα από 128
Μερικά νέα στοιχεία έναρξης είναι μικρότερα από 128 και αργότερα γίνονται μεγαλύτερα από 128
Ας υποθέσουμε ότι η πρόβλεψη θα αναλαμβάνει πάντα τον πραγματικό κλάδο στην πρώτη εκτέλεση.
Έτσι, στην πρώτη περίπτωση, θα ισχύει πάντα το αληθινόκλάδο δεδομένου ότι ιστορικά όλες οι προβλέψεις του είναι σωστές.
Στη 2η περίπτωση, αρχικά θα προβλέψει λάθος, αλλά μετά από μερικές επαναλήψεις, θα προβλέψει σωστά.
Στην 3η περίπτωση, αρχικά θα προβλεφθεί σωστά έως ότου τα στοιχεία είναι μικρότερα από 128. Μετά από αυτό θα αποτύχει για κάποιο χρονικό διάστημα και το σωστό όταν βλέπει αποτυχία πρόβλεψης κλάδου στην ιστορία.
Σε όλες αυτές τις περιπτώσεις η αποτυχία θα είναι πολύ μικρότερη σε αριθμό και ως αποτέλεσμα, μόνο μερικές φορές θα χρειαστεί να απορρίψει τις μερικώς εκτελεσθείσες οδηγίες και να ξεκινήσει εκ νέου με το σωστό κλάδο, με αποτέλεσμα λιγότερους κύκλους CPU.
Αλλά σε περίπτωση τυχαίου μη ταξινομημένου πίνακα, η πρόβλεψη θα πρέπει να απορρίψει τις μερικώς εκτελεσμένες οδηγίες και να ξεκινήσει ξανά με τον σωστό κλάδο τις περισσότερες φορές και να οδηγήσει σε περισσότερους κύκλους CPU σε σύγκριση με τον ταξινομημένο πίνακα.
|
Μια επίσημη απάντηση θα ήταν από
Intel - Αποφυγή του κόστους της παραπληροφόρησης κλάδου
Intel - Αναδιοργάνωση υποκαταστημάτων και βρόχων για την αποτροπή λαθών
Επιστημονικές εργασίες - αρχιτεκτονική υπολογιστών πρόβλεψης κλάδου
Βιβλία: J.L. Hennessy, D.A. Patterson: Αρχιτεκτονική υπολογιστών: μια ποσοτική προσέγγιση
Άρθρα σε επιστημονικές δημοσιεύσεις: Τ.Υ. Ναι, Υ.Ν. Ο Patt έκανε πολλά από αυτά σε προβλέψεις κλάδου.
Μπορείτε επίσης να δείτε από αυτό το υπέροχο διάγραμμα γιατί η πρόβλεψη κλάδου μπερδεύεται.
Κάθε στοιχείο στον αρχικό κώδικα είναι μια τυχαία τιμή
δεδομένα [c] = std :: rand ()% 256;
έτσι ο προβλεπόμενος θα αλλάξει πλευρές καθώς το std :: rand () χτυπά.
Από την άλλη πλευρά, μόλις ταξινομηθεί, ο προβλεπόμενος θα μετακινηθεί αρχικά σε μια κατάσταση που δεν έχει ληφθεί έντονα και όταν οι τιμές αλλάξουν στην υψηλή τιμή, ο προβλεπόμενος θα αλλάξει σε τρία στάδια, αλλάζει από την ένταση που δεν λαμβάνεται σε έντονη λήψη.
|
Στην ίδια γραμμή (νομίζω ότι αυτό δεν τονίστηκε με καμία απάντηση) είναι καλό να αναφέρουμε ότι μερικές φορές (ειδικά σε λογισμικό όπου η απόδοση έχει σημασία - όπως στον πυρήνα του Linux) μπορείτε να βρείτε κάποιες αν δηλώσεις όπως τα ακόλουθα:
εάν (πιθανό (everything_is_ok))
{
/* Κάνε κάτι */
}
ή παρόμοια:
εάν (απίθανο (very_improbable_condition))
{
/* Κάνε κάτι */
}
Τόσο πιθανό () όσο και απίθανο () είναι στην πραγματικότητα μακροεντολές που ορίζονται χρησιμοποιώντας κάτι σαν το __builtin_expect του GCC για να βοηθήσουν τον μεταγλωττιστή να εισαγάγει τον κωδικό πρόβλεψης για να ευνοήσει την κατάσταση λαμβάνοντας υπόψη τις πληροφορίες που παρέχονται από τον χρήστη. Το GCC υποστηρίζει άλλες ενσωματωμένες δυνατότητες που θα μπορούσαν να αλλάξουν τη συμπεριφορά του προγράμματος που εκτελείται ή να εκπέμψουν οδηγίες χαμηλού επιπέδου, όπως εκκαθάριση της προσωρινής μνήμης κ.λπ. Δείτε αυτήν την τεκμηρίωση που περνά από τα διαθέσιμα ενσωματωμένα στοιχεία του GCC.
Κανονικά, αυτό το είδος βελτιστοποιήσεων βρίσκεται κυρίως σε εφαρμογές σε πραγματικό χρόνο ή σε ενσωματωμένα συστήματα όπου ο χρόνος εκτέλεσης έχει σημασία και είναι κρίσιμος. Για παράδειγμα, εάν ελέγχετε για κάποια κατάσταση σφάλματος που συμβαίνει μόνο 1/10000000 φορές, τότε γιατί να μην ενημερώσετε τον μεταγλωττιστή σχετικά με αυτό; Με αυτόν τον τρόπο, από προεπιλογή, η πρόβλεψη κλάδου θα υποθέσει ότι η συνθήκη είναι ψευδής.
|
Συχνά χρησιμοποιούμενες λειτουργίες Boolean στο C ++ παράγουν πολλά υποκαταστήματα στο μεταγλωττισμένο πρόγραμμα. Εάν αυτοί οι κλάδοι βρίσκονται μέσα σε βρόχους και είναι δύσκολο να προβλεφθούν, μπορούν να επιβραδύνουν σημαντικά την εκτέλεση. Οι δυαδικές μεταβλητές αποθηκεύονται ως ακέραιοι 8-bit με την τιμή 0 για false και 1 για true.
Οι δυαδικές μεταβλητές είναι υπερβολικά καθορισμένες με την έννοια ότι όλοι οι τελεστές που έχουν μεταβλητές Boolean ως είσοδος ελέγχουν αν οι είσοδοι έχουν άλλη τιμή εκτός από 0 ή 1, αλλά οι τελεστές που έχουν Booleans ως έξοδο δεν μπορούν να παράγουν άλλη τιμή από 0 ή 1. Αυτό καθιστά τις λειτουργίες με Οι δυαδικές μεταβλητές ως είσοδο λιγότερο αποτελεσματικές από ό, τι είναι απαραίτητο.
Εξετάστε το παράδειγμα:
bool a, b, c, d;
c = α && b;
d = α || σι;
Αυτό συνήθως εφαρμόζεται από τον μεταγλωττιστή με τον ακόλουθο τρόπο:
bool a, b, c, d;
αν (a! = 0) {
αν (b! = 0) {
c = 1;
}
αλλιώς {
πηγαίνετε CFALSE;
}
}
αλλιώς {
CFALSE:
c = 0;
}
αν (a == 0) {
αν (b == 0) {
d = 0;
}
αλλιώς {
μετάβαση DTRUE;
}
}
αλλιώς {
DTRUE:
d = 1;
}
Αυτός ο κωδικός απέχει πολύ από τον βέλτιστο. Τα υποκαταστήματα ενδέχεται να χρειαστούν πολύ χρόνο σε περίπτωση εσφαλμένων προβλέψεων. Οι λειτουργίες Boolean μπορούν να γίνουν πολύ πιο αποτελεσματικές εάν είναι γνωστό με βεβαιότητα ότι οι τελεστές δεν έχουν άλλες τιμές από το 0 και 1. Ο λόγος για τον οποίο ο μεταγλωττιστής δεν κάνει τέτοια υπόθεση είναι ότι οι μεταβλητές ενδέχεται να έχουν άλλες τιμές εάν δεν είναι αρχικοποιημένες ή προέρχονται από άγνωστες πηγές. Ο παραπάνω κώδικας μπορεί να βελτιστοποιηθεί εάν το a και b έχει αρχικοποιηθεί σε έγκυρες τιμές ή εάν προέρχονται από χειριστές που παράγουν έξοδο Boolean. Ο βελτιστοποιημένος κώδικας μοιάζει με αυτόν:
char a = 0, b = 1, c, d;
c = α & β;
δ = α | σι;
Το char χρησιμοποιείται αντί του bool για να καταστεί δυνατή η χρήση των τελεστών (& και |) αντί των τελεστών Boolean (&& και ||). Οι τελεστές bitwise είναι μεμονωμένες οδηγίες που χρειάζονται μόνο έναν κύκλο ρολογιού. Ο τελεστής OR (|) λειτουργεί ακόμη και αν το a και b έχει άλλες τιμές εκτός από 0 ή 1. Ο τελεστής AND (&) και ο τελεστής EXCLUSIVE OR (^) μπορεί να δώσει ασυνεπή αποτελέσματα εάν οι τελεστές έχουν άλλες τιμές εκτός από 0 και 1
~ δεν μπορεί να χρησιμοποιηθεί για ΟΧΙ. Αντι αυτου,μπορείτε να δημιουργήσετε ένα Boolean NOT σε μια μεταβλητή που είναι γνωστό ότι είναι 0 ή 1 με το XOR'ing με 1:
bool a, b;
β =! α;
μπορεί να βελτιστοποιηθεί για:
char a = 0, b;
b = α ^ 1;
a && b δεν μπορεί να αντικατασταθεί με a & b αν το b είναι μια έκφραση που δεν θα πρέπει να αξιολογηθεί εάν το a είναι ψευδές (&& δεν θα αξιολογήσει το b, & will). Ομοίως, ένα || b δεν μπορεί να αντικατασταθεί με | b αν το b είναι μια έκφραση που δεν πρέπει να αξιολογηθεί εάν το α είναι αλήθεια.
Η χρήση τελεστών bitwise είναι πιο πλεονεκτική εάν οι τελεστές είναι μεταβλητές από ότι εάν οι τελεστές είναι συγκρίσεις:
bool a; διπλό x, y, z;
a = x> y && z <5.0;
είναι βέλτιστο στις περισσότερες περιπτώσεις (εκτός αν περιμένετε ότι το && express θα δημιουργήσει πολλές εσφαλμένες προβλέψεις κλάδου).
|
Αυτό είναι σίγουρο!...
Η πρόβλεψη διακλάδωσης καθιστά τη λογική λειτουργία πιο αργή, λόγω της αλλαγής που συμβαίνει στον κώδικά σας! Είναι σαν να πηγαίνετε σε έναν ίσιο δρόμο ή έναν δρόμο με πολλές στροφές, σίγουρα ο ευθείος θα γίνει πιο γρήγορα! ...
Εάν ο πίνακας έχει ταξινομηθεί, η κατάστασή σας είναι λανθασμένη στο πρώτο βήμα: data [c]> = 128 και στη συνέχεια γίνεται πραγματική τιμή για ολόκληρο το δρόμο μέχρι το τέλος του δρόμου. Έτσι φτάνετε πιο γρήγορα στο τέλος της λογικής. Από την άλλη πλευρά, χρησιμοποιώντας έναν μη ταξινομημένο πίνακα, χρειάζεστε πολλή στροφή και επεξεργασία που κάνουν τον κώδικά σας πιο αργό σίγουρα ...
Κοιτάξτε την εικόνα που δημιούργησα για εσάς παρακάτω. Ποιος δρόμος θα τελειώσει πιο γρήγορα;
Έτσι, μέσω προγραμματισμού, η πρόβλεψη κλάδου προκαλεί τη διαδικασία πιο αργή ...
Επίσης στο τέλος, είναι καλό να γνωρίζουμε ότι έχουμε δύο είδη προβλέψεων κλάδου ότι το καθένα θα επηρεάσει διαφορετικά τον κώδικά σας:
1. Στατικός
2. Δυναμική
Η πρόβλεψη στατικού κλάδου χρησιμοποιείται από τον μικροεπεξεργαστή την πρώτη φορά
αντιμετωπίζεται ένας υποκατάστημα υπό όρους και είναι δυναμική πρόβλεψη κλάδου
χρησιμοποιείται για την επιτυχή εκτέλεση του υπό όρους κωδικού κλάδου.
Για να γράψετε αποτελεσματικά τον κωδικό σας για να επωφεληθείτε από αυτούς
κανόνες, όταν γράφετε if-else ή αλλάζετε δηλώσεις, ελέγξτε περισσότερο
κοινές περιπτώσεις πρώτα και σταδιακά δουλεύουν στα λιγότερο κοινά.
Οι βρόχοι δεν απαιτούν απαραίτητα καμία ειδική σειρά κωδικών για
στατική πρόβλεψη κλάδου, καθώς μόνο η κατάσταση του επαναληπτικού βρόχου
χρησιμοποιείται συνήθως.
|
Αυτή η ερώτηση έχει ήδη απαντηθεί άριστα πολλές φορές. Ακόμα θα ήθελα να επιστήσω την προσοχή της ομάδας σε μια άλλη ενδιαφέρουσα ανάλυση.
Πρόσφατα αυτό το παράδειγμα (τροποποιήθηκε πολύ ελαφρώς) χρησιμοποιήθηκε επίσης ως τρόπος για να δείξει πώς ένα κομμάτι κώδικα μπορεί να γίνει προφίλ στο ίδιο το πρόγραμμα στα Windows. Στην πορεία, ο συγγραφέας δείχνει επίσης πώς να χρησιμοποιήσει τα αποτελέσματα για να προσδιορίσει πού ο κώδικας ξοδεύει το μεγαλύτερο μέρος του χρόνου του τόσο στην ταξινομημένη όσο και στη μη ταξινομημένη περίπτωση. Τέλος, το κομμάτι δείχνει επίσης πώς να χρησιμοποιήσετε ένα λίγο γνωστό χαρακτηριστικό του HAL (Hardware Abstraction Layer) για να προσδιορίσετε πόση παραπλανητική διακλάδωση συμβαίνει στην μη ταξινομημένη περίπτωση.
Ο σύνδεσμος είναι εδώ:
Μια επίδειξη αυτο-προφίλ
|
Όπως έχει ήδη αναφερθεί από άλλους, αυτό που κρύβεται πίσω από το μυστήριο είναι το Branch Predictor.
Δεν προσπαθώ να προσθέσω κάτι αλλά να εξηγήσω την ιδέα με άλλο τρόπο.
Υπάρχει μια συνοπτική εισαγωγή στο wiki που περιέχει κείμενο και διάγραμμα.
Μου αρέσει η εξήγηση παρακάτω που χρησιμοποιεί ένα διάγραμμα για να επεξεργαστεί το Branch Predictor διαισθητικά.
Στην αρχιτεκτονική υπολογιστών, ένας προγνωστικός κλάδος είναι ένας
ψηφιακό κύκλωμα που προσπαθεί να μαντέψει με ποιον τρόπο ένα υποκατάστημα (π.χ.
if-then-else δομή) θα προχωρήσει πριν είναι σίγουρα γνωστό. ο
Ο σκοπός του προγνωστικού κλάδου είναι να βελτιώσει τη ροή στο
αγωγός οδηγιών. Οι προγνωστικοί κλάδοι παίζουν κρίσιμο ρόλο
επιτυγχάνοντας υψηλή αποτελεσματική απόδοση σε πολλούς σύγχρονους αγωγούς
αρχιτεκτονικές μικροεπεξεργαστών, όπως x86.
Η αμφίδρομη διακλάδωση πραγματοποιείται συνήθως με ένα άλμα υπό όρους
εντολή. Ένα υπό όρους άλμα μπορεί είτε να "δεν ληφθεί" και να συνεχιστεί
εκτέλεση με τον πρώτο κλάδο κώδικα που ακολουθεί αμέσως
μετά από το άλμα υπό όρους, ή μπορεί να "ληφθεί" και να μεταβείτε σε ένα
διαφορετική θέση στη μνήμη προγράμματος όπου είναι ο δεύτερος κλάδος του κώδικα
αποθηκευμένο. Δεν είναι γνωστό με βεβαιότητα εάν θα είναι ένα υπό όρους άλμα
λαμβάνεται ή δεν έχει ληφθεί έως ότου υπολογιστεί η κατάσταση και το
το υπό όρους άλμα έχει περάσει το στάδιο εκτέλεσης της εντολής
αγωγός (βλέπε σχήμα 1).
Με βάση το περιγραφόμενο σενάριο, έγραψα μια επίδειξη κινουμένων σχεδίων για να δείξω πώς οι οδηγίες εκτελούνται σε αγωγό σε διαφορετικές καταστάσεις.
Χωρίς τον προγνωστικό κλάδο.
Χωρίς πρόβλεψη κλάδου, ο επεξεργαστής θα πρέπει να περιμένει μέχρι το
Η εντολή άλματος υπό όρους έχει περάσει το στάδιο εκτέλεσης πριν από το
η επόμενη οδηγία μπορεί να εισέλθει στο στάδιο ανάκτησης στον αγωγό.
Το παράδειγμα περιέχει τρεις οδηγίες και η πρώτη είναι μια εντολή άλματος υπό όρους. Οι δύο τελευταίες οδηγίες μπορούν να περάσουν στον αγωγό έως ότου εκτελεστεί η εντολή άλματος υπό όρους.
Θα χρειαστούν 9 κύκλοι ρολογιού για να ολοκληρωθούν 3 οδηγίες.
Χρησιμοποιήστε το Branch Predictor και μην κάνετε άλμα υπό όρους. Ας υποθέσουμε ότι η πρόβλεψη δεν παίρνει τουπό όρους άλμα.
Θα χρειαστούν 7 κύκλοι ρολογιού για να ολοκληρωθούν 3 οδηγίες.
Χρησιμοποιήστε το Branch Predictor και κάντε ένα άλμα υπό όρους. Ας υποθέσουμε ότι η πρόβλεψη δεν κάνει το άλμα υπό όρους.
Θα χρειαστούν 9 κύκλοι ρολογιού για να ολοκληρωθούν 3 οδηγίες.
Ο χρόνος που χάνεται σε περίπτωση εσφαλμένης πρόβλεψης κλάδου ισούται με
ο αριθμός των σταδίων που βρίσκονται σε εξέλιξη από το στάδιο ανάκτησης έως το
εκτελέστε το στάδιο. Οι σύγχρονοι μικροεπεξεργαστές τείνουν να έχουν αρκετά μεγάλο χρονικό διάστημα
αγωγούς έτσι ώστε η καθυστέρηση ανακριβείας να είναι μεταξύ 10 και 20 ρολογιού
κύκλους. Ως αποτέλεσμα, η κατασκευή ενός αγωγού αυξάνει περισσότερο την ανάγκη για α
πιο προηγμένη πρόβλεψη κλάδου.
Όπως μπορείτε να δείτε, φαίνεται ότι δεν έχουμε λόγο να μην χρησιμοποιήσουμε το Branch Predictor.
Είναι μια απλή επίδειξη που διευκρινίζει το πολύ βασικό μέρος του Branch Predictor. Εάν αυτά τα gif είναι ενοχλητικά, μη διστάσετε να τα καταργήσετε από την απάντηση και οι επισκέπτες μπορούν επίσης να λάβουν τον ζωντανό πηγαίο κώδικα επίδειξης από το BranchPredictorDemo
|
Κέρδος πρόβλεψης κλάδου!
Είναι σημαντικό να κατανοήσουμε ότι η εσφαλμένη πρόβλεψη των κλάδων δεν επιβραδύνει τα προγράμματα. Το κόστος μιας χαμένης πρόβλεψης είναι σαν να μην υπήρχε πρόβλεψη κλάδου και περιμένατε την αξιολόγηση της έκφρασης να αποφασίσει ποιος κώδικας θα εκτελεστεί (περαιτέρω εξήγηση στην επόμενη παράγραφο).
εάν (έκφραση)
{
// Εκτέλεση 1
} αλλιώς {
// Εκτέλεση 2
}
Όποτε υπάρχει μια δήλωση if-else \ switch, η έκφραση πρέπει να αξιολογηθεί για να προσδιοριστεί ποιο μπλοκ πρέπει να εκτελεστεί. Στον κωδικό συναρμολόγησης που δημιουργείται από τον μεταγλωττιστή, εισάγονται οδηγίες υπό όρους διακλάδωσης.
Μια εντολή κλάδου μπορεί να κάνει τον υπολογιστή να αρχίσει να εκτελεί μια διαφορετική ακολουθία εντολών και, επομένως, να αποκλίνει από την προεπιλεγμένη συμπεριφορά εκτέλεσης εντολών με τη σειρά (δηλαδή εάν η έκφραση είναι λανθασμένη, το πρόγραμμα παραλείπει τον κωδικό του μπλοκ if) ανάλογα με κάποια κατάσταση είναι η εκτίμηση έκφρασης στην περίπτωσή μας.
Τούτου λεχθέντος, ο μεταγλωττιστής προσπαθεί να προβλέψει το αποτέλεσμα προτού πραγματικά αξιολογηθεί. Θα πάρει οδηγίες από το μπλοκ if, και αν η έκφραση αποδειχθεί αληθινή, τότε υπέροχο! Κερδίσαμε το χρόνο που χρειάστηκε για να τον αξιολογήσουμε και σημειώσαμε πρόοδο στον κώδικα. Αν όχι τότε εκτελούμε λάθος κωδικό, ο αγωγός ξεπλένεται και εκτελείται το σωστό μπλοκ.
Οραματισμός:
Ας υποθέσουμε ότι πρέπει να επιλέξετε τη διαδρομή 1 ή τη διαδρομή 2. Περιμένοντας τον σύντροφό σας να ελέγξει το χάρτη, σταματήσατε στο ## και περιμένατε, ή θα μπορούσατε απλά να επιλέξετε τη διαδρομή1 και αν ήσασταν τυχεροί (η διαδρομή 1 είναι η σωστή διαδρομή), τότε υπέροχο δεν χρειάστηκε να περιμένετε τον σύντροφό σας να ελέγξει τον χάρτη (εξοικονομήσατε χρόνο που θα του χρειαζόταν να ελέγξει τον χάρτη), διαφορετικά θα γυρίσετε πίσω.
Ενώ το ξεπλύσιμο των αγωγών είναι εξαιρετικά γρήγορο, αξίζει τον κόπο να παίρνουμε σήμερα το στοίχημα. Η πρόβλεψη ταξινομημένων δεδομένων ή δεδομένων που αλλάζουν αργά είναι πάντα ευκολότερη και καλύτερη από την πρόβλεψη γρήγορων αλλαγών.
O Διαδρομή 1 / -------------------------------
/ | \ /
| --------- ## /
/ \ \
\
Διαδρομή 2 \ --------------------------------
|
Στο ARM, δεν απαιτείται κλάδος, επειδή κάθε εντολή έχει ένα πεδίο συνθήκης 4-bit, το οποίο ελέγχει (με μηδενικό κόστος) οποιαδήποτε από τις 16 διαφορετικές συνθήκες που ενδέχεται να προκύψουν στο Μητρώο κατάστασης επεξεργαστή και εάν η συνθήκη σε μια εντολή είναι λανθασμένη, η οδηγία παραλείπεται. Αυτό εξαλείφει την ανάγκη για σύντομους κλάδους και δεν θα υπήρχε επιτυχία πρόβλεψης κλάδου για αυτόν τον αλγόριθμο. Επομένως, η ταξινομημένη έκδοση αυτού του αλγορίθμου θα λειτουργούσε πιο αργά από την μη ταξινομημένη έκδοση στο ARM, λόγω του επιπλέον γενικού διαλογής.
Ο εσωτερικός βρόχος για αυτόν τον αλγόριθμο θα μοιάζει με τον ακόλουθο στη γλώσσα συναρμολόγησης ARM:
MOV R0, # 0 // R0 = άθροισμα = 0
MOV R1, # 0 // R1 = c = 0
ADR R2, data // R2 = addr του πίνακα δεδομένων (βάλτε αυτήν την οδηγία έξω από τον εξωτερικό βρόχο)
.inner_loop // Ετικέτα διακλάδωσης εσωτερικού βρόχου
LDRB R3, [R2, R1] // R3 = δεδομένα [c]
CMP R3, # 128 // σύγκριση R3 έως 128
ΠΡΟΣΘΗΚΗ R0, R0, R3 // εάν R3> = 128, τότε άθροισμα + = δεδομένα [c] - δεν απαιτείται κλάδος!
ΠΡΟΣΘΗΚΗ R1, R1, # 1 // c ++
CMP R1, #arraySize // σύγκριση c με arraySize
BLT inner_loop // Διακλάδωση σε inner_loop εάν c  ());
για (χωρίς υπογραφή c = 0; c  = 128
άθροισμα = άθροισμα + δεδομένα1 (j);
τέλος
τέλος
τέλος
toc;
ExeTimeWithSorting = toc - tic;
Τα αποτελέσματα για τον παραπάνω κωδικό MATLAB έχουν ως εξής:
α: Χρόνος που πέρασε (χωρίς ταξινόμηση) = 3479.880861 δευτερόλεπτα.
β: Χρόνος που έχει παρέλθει (με ταξινόμηση) = 2377.873098 δευτερόλεπτα.
Τα αποτελέσματα του κώδικα C όπως στο @GManNickG παίρνω:
α: Χρόνος που πέρασε (χωρίς ταξινόμηση) = 19,8761 δευτ.
b: Χρόνος που πέρασε (με ταξινόμηση) = 7.37778 δευτ.
Με βάση αυτό, φαίνεται ότι το MATLAB είναι σχεδόν 175 φορές πιο αργό από την εφαρμογή C χωρίς ταξινόμηση και 350 φορές πιο αργό με ταξινόμηση. Με άλλα λόγια, το αποτέλεσμα (της πρόβλεψης κλάδου) είναι 1,46x για την εφαρμογή MATLAB και 2,7x για την εφαρμογή C.
|
Η υπόθεση από άλλες απαντήσεις ότι κάποιος πρέπει να ταξινομήσει τα δεδομένα δεν είναι σωστή.
Ο ακόλουθος κώδικας δεν ταξινομεί ολόκληρο τον πίνακα, αλλά μόνο τμήματα 200 στοιχείων αυτού, και έτσι τρέχει το γρηγορότερο.
Η ταξινόμηση μόνο των τμημάτων k-element ολοκληρώνει την προεπεξεργασία σε γραμμικό χρόνο, O (n), και όχι ο O (n.log (n)) χρόνος που απαιτείται για την ταξινόμηση ολόκληρου του πίνακα.
# συμπερίληψη <αλγόριθμος>
# συμπερίληψη 
# συμπερίληψη 
int main () {
int δεδομένα [32768]; const int l = sizeof data / sizeof data [0];
για (χωρίς υπογραφή c = 0; c  = 128)
άθροισμα + = δεδομένα [c];
}
}
std :: cout << static_cast  (ρολόι () - έναρξη) / CLOCKS_PER_SEC << std :: endl;
std :: cout << "sum =" << άθροισμα << std :: endl;
}
Αυτό επίσης "αποδεικνύει" ότι δεν έχει καμία σχέση με αλγοριθμικό ζήτημα όπως η ταξινόμηση, και είναι πράγματι πρόβλεψη κλάδου.
|
Απάντηση του Bjarne Stroustrup σε αυτήν την ερώτηση:
Αυτό ακούγεται σαν μια ερώτηση συνέντευξης. Είναι αλήθεια? Πώς θα ήξερες? Είναι κακή ιδέα να απαντήσετε σε ερωτήσεις σχετικά με την αποτελεσματικότητα χωρίς πρώτα να κάνετε μερικές μετρήσεις, επομένως είναι σημαντικό να γνωρίζετε πώς να μετρήσετε.
Έτσι, δοκίμασα με ένα διάνυσμα εκατομμυρίων ακεραίων και πήρα:
Έχει ήδη ταξινομηθεί 32995 χιλιοστά του δευτερολέπτου
Ανακάτεμα 125944 χιλιοστά του δευτερολέπτου
Έχει ήδη ταξινομηθεί 18610 χιλιοστά του δευτερολέπτου
Ανακάτεψε 133304 χιλιοστά του δευτερολέπτου
Έχει ήδη ταξινομηθεί 17942 χιλιοστά του δευτερολέπτου
Ανακάτεψε 107858 χιλιοστά του δευτερολέπτου
Έτρεξα αυτό μερικές φορές για να είμαι σίγουρος. Ναι, το φαινόμενο είναι πραγματικό. Ο κωδικός κλειδιού μου ήταν:
void run (διάνυσμα  & v, const string & label)
{
auto t0 = system_clock :: τώρα ();
ταξινόμηση (v.begin (), v.end ());
auto t1 = system_clock :: τώρα ();
<< ετικέτα
<< διάρκεια_ εκπομπή <μικροδευτερόλεπτα> (t1 - t0). αριθμός ()
<< "χιλιοστά του δευτερολέπτου \ n";
}
άκυρο tst ()
{
διάνυσμα  v (1'000'000);
iota (v.begin (), v.end (), 0);
run (v, "ήδη ταξινομημένο");
std :: shuffle (v.begin (), v.end (), std :: mt19937 {std :: random_device {} ()});
εκτέλεση (v, "ανακατεμένο");
}
Τουλάχιστον το φαινόμενο είναι πραγματικό με αυτόν τον μεταγλωττιστή, την τυπική βιβλιοθήκη και τις ρυθμίσεις βελτιστοποίησης. Διαφορετικές υλοποιήσεις μπορούν και δίνουν διαφορετικές απαντήσεις. Στην πραγματικότητα, κάποιος έκανε μια πιο συστηματική μελέτη (μια γρήγορη αναζήτηση στο Διαδίκτυο θα το βρει) και οι περισσότερες εφαρμογές δείχνουν αυτό το αποτέλεσμα.
Ένας λόγος είναι η πρόβλεψη κλάδου: η λειτουργία κλειδιού στον αλγόριθμο ταξινόμησης είναι «if (v [i]  = 128. Αυτό σημαίνει ότι μπορούμε εύκολα να εξαγάγουμε ένα μόνο κομμάτι που θα μας πει αν θέλουμε μια τιμή ή όχι: μετατοπίζοντας τα δεδομένα στα δεξιά 7 bits, μένουν με 0 bit ή 1 bit και θέλουμε να προσθέσουμε την τιμή μόνο όταν έχουμε 1 bit. Ας το ονομάσουμε αυτό το κομμάτι "bit απόφασης".
Χρησιμοποιώντας την τιμή 0/1 του bit απόφασης ως ευρετήριο σε έναν πίνακα, μπορούμε να φτιάξουμε κώδικα που θα είναι εξίσου γρήγορος είτε τα δεδομένα ταξινομούνται είτε όχι. Ο κώδικάς μας θα προσθέτει πάντα μια τιμή, αλλά όταν το bit απόφασης είναι 0, θα προσθέσουμε την τιμή κάπου που δεν μας ενδιαφέρει. Εδώ είναι ο κωδικός:
// Δοκιμή
clock_t start = ρολόι ();
πολύ καιρό a [] = {0, 0};
πολύ μεγάλο ποσό
για (χωρίς υπογραφή i = 0; i <100000; ++ i)
{
// Κύριος βρόχος
για (χωρίς υπογραφή c = 0; c > 7);
a [j] + = δεδομένα [c];
}
}
double elapsedTime = static_cast  (ρολόι () - έναρξη) / CLOCKS_PER_SEC;
άθροισμα = α [1];
Αυτός ο κώδικας σπαταλά τα μισά από τα πρόσθετα αλλά δεν έχει ποτέ αποτυχία πρόβλεψης κλάδου. Είναι πολύ πιο γρήγορα σε τυχαία δεδομένα από την έκδοση με μια πραγματική δήλωση if.
Αλλά στις δοκιμές μου, ένας σαφής πίνακας αναζήτησης ήταν ελαφρώς πιο γρήγορος από αυτό, πιθανώς επειδή η ευρετηρίαση σε έναν πίνακα αναζήτησης ήταν ελαφρώς πιο γρήγορη από την αλλαγή bit. Αυτό δείχνει τον τρόπο με τον οποίο ο κώδικάς μου δημιουργεί και χρησιμοποιεί τον πίνακα αναζήτησης (χωρίς φαντασία ονομάζεται lut για το "LookUp Table" στον κώδικα). Εδώ είναι ο κωδικός C ++:
// Δηλώστε και, στη συνέχεια, συμπληρώστε τον πίνακα αναζήτησης
int lut [256];
για (χωρίς υπογραφή c = 0; c <256; ++ c)
lut [c] = (c> = 128); γ: 0;
// Χρησιμοποιήστε τον πίνακα αναζήτησης μετά τη δημιουργία του
για (χωρίς υπογραφή i = 0; i <100000; ++ i)
{
// Κύριος βρόχος
για (χωρίς υπογραφή c = 0; c )
κόμβος = κόμβος-> pLeft;
αλλού
node = node-> pRight;
αυτή η βιβλιοθήκη θα έκανε κάτι σαν:
i = (x  τιμή);
node = node-> σύνδεσμος [i];
Είναι μια ωραία λύση και ίσως θα λειτουργήσει.
|
Πολύ ενεργή ερώτηση. Κερδίστε 10 φήμη για να απαντήσετε σε αυτήν την ερώτηση. Η απαίτηση φήμης συμβάλλει στην προστασία αυτής της ερώτησης από ανεπιθύμητες ενέργειες και μη απαντήσεις.
Δεν είναι η απάντηση που ψάχνετε; Περιηγηθείτε σε άλλες ερωτήσεις με ετικέτα Java-C ++ βελτιστοποίηση απόδοσης-πρόβλεψη κλάδου ή κάντε τη δική σας ερώτηση.